package 剑指Offer.easy;

import java.util.Deque;
import java.util.LinkedList;

public class 滑动窗口的最大值 {
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0 || k > nums.length) {
                return new int[0];
            }
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> deque = new LinkedList<>();
            //初始化滑动窗口
            for (int i = 0; i < k; i++) {
                while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                    deque.pollLast();
                }
                deque.addLast(nums[i]);
            }
            int index = 0;
            res[index++] = deque.peekFirst();
            //滑动
            for (int i = k; i < nums.length; i++) {
                //如果前一个窗口初值为最大值，那现在已经过期，需要剔除；如果不是，说明最大值还在窗口内
                if (nums[i - k] == deque.peekFirst()) {
                    deque.pollFirst();
                }
                //保持队列的单调递减性
                while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                    deque.pollLast();
                }
                deque.addLast(nums[i]);
                //添加当前窗口的最大值
                res[index++] = deque.peekFirst();
            }
            return res;
        }
    }
}
